%
%function resTrees = extractSolution(AoT)
% this function implements the DP algorithm to extract solution from an IG
% computed AoT.
%n_vol_and = length(unique(AoT.vol_and_cluster));
%nLevel= size(AoT.orLayer,1);
%andLayer = AoT.andLayer;
%orLayer  = AoT.orLayer;
%termLayer = AoT.termLayer;
function resTrees = extractSolution(n_vol_and,andLayer,orLayer,termLayer)

resTrees=cell(n_vol_and,1); % as collection of volAND node
% auxilary data structure
aux_and_layer = cell(size(andLayer));
for iLevel = 1:size(andLayer,1)
    aux_and_layer{iLevel}=struct('score',{},'diffInDepth',{});
end
for i_val_and = 1:n_vol_and
	nLevel=size(orLayer,1);
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % Section 1. bottom up pass
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    for iLevel = 1:nLevel
        %% and layer
        n_node = size(andLayer{iLevel},1);
        for i_node= 1:n_node
            ch1  =[];
            ch2 = [];
            node = andLayer{iLevel}(i_node,:);
            aux_node = struct('score',[],'diffInDepth',[]);
            if node(1)~=0 && node(2) ~=0
                ch1 = orLayer{node(1)}(node(2));
            end
            if node(3)~=0 && node(4) ~=0
                ch2 = orLayer{node(3)}(node(4));
            end
            
            if ~isempty(ch1)&& ~isempty(ch2)
                if ch1.corner(3)~=ch2.corner(3)
                    % difference in depth, choose the max node
					[val ind]= max([ch1.score ch2.score]);
					aux_node.score = val;
					aux_node.diffInDepth = ind;
                else
                    aux_node.diffInDepth = 0;
                    aux_node.score = ch1.score+ch2.score;
                end
            elseif isempty(ch1) && isempty(ch2)
                % in thsi case, both child nodes are not valid OR node.
                % this might be possible if none of them satisfies the aspect
                % ratio constraint
                % disp('warning, all children nodes are empty')
                aux_node.diffInDepth =0;
                aux_node.score = -Inf;
            else
                if isempty(ch1)
                    aux_node.score = ch2.score;
                else
                    aux_node.score = ch1.score;
                end
                aux_node.diffInDepth = 0;
            end
            aux_and_layer{iLevel}(i_node) =aux_node;% score and if diffIndepth
        end
        %% or layer
        n_node = size(orLayer{iLevel},2);
        for i_node =1:n_node
            node = orLayer{iLevel}(i_node);
            chd_scores = zeros(length(node.children)+1,1);
            for i_chd = 1:length(node.children)
                i_and_chd= node.children(i_chd);
                chd_scores(i_chd) = aux_and_layer{iLevel}(i_and_chd).score;
            end
            chd_scores(end) = termLayer{iLevel}(i_node).score(i_val_and);
            [score ind]=max(chd_scores);
            node.score= score;
            if ind == length(chd_scores) % choose terminal node
                node.argmax=0;
            else
                node.argmax = node.children(ind);
            end
            orLayer{iLevel}(i_node).argmax=node.argmax;
            orLayer{iLevel}(i_node).score = node.score;
        end
        
    end
    
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % Section 2. top down pass
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    res_or_layer = cell(nLevel,1);
    res_and_layer = cell(nLevel,1);
    res_aux_and_layer = cell(nLevel,1);
    res_term_layer = cell(nLevel,1);
    for iLevel = 1:nLevel
        res_term_layer{iLevel} = struct('type',{},'corner',{},'dim',{},'children',{},...
            'parent',{},'R',{},'plane',{},'score_map',{},'arg_max_map',{},'score',{},'shape_ind',{});
    end
    
    %% initialize the top layer in result graph
    res_or_layer{nLevel}=orLayer{nLevel};
    n_node =  size(res_or_layer{iLevel},1);
    for i_node = 1:n_node
        res_or_layer{nLevel}(i_node)=orLayer{nLevel}(i_node);
        res_or_layer{nLevel}(i_node).org_index =i_node; % node's index in orLayer of AoT
        res_or_layer{nLevel}(i_node).org_argmax =  res_or_layer{nLevel}(i_node).argmax;
    end
    
       
    %% top down from top layer
    for iLevel = nLevel:-1:1;
        n_node =  size(res_or_layer{iLevel},1);
        
        for i_node = 1:n_node
            node= res_or_layer{iLevel}(i_node);
            % find arg max in or layer, and push new and nodes which are to be
            % explotred.
            if node.argmax== 0 % terminal node
                res_term_layer{iLevel}(i_node)=termLayer{iLevel}(node.org_index);
                node.org_argmax = 0;
            else
                res_and_layer{iLevel} = [res_and_layer{iLevel}; andLayer{iLevel}(node.argmax,:)];
                res_aux_and_layer{iLevel} =[res_aux_and_layer{iLevel}; aux_and_layer{iLevel}(node.argmax)];
                node.org_argmax = node.argmax;
                node.argmax = size(res_and_layer{iLevel},1);
            end
            res_or_layer{iLevel}(i_node)=node;
        end
        
        n_node = size(res_and_layer{iLevel},1);
        for i_node = 1:n_node
            node = res_and_layer{iLevel}(i_node,:);
            aux_node = res_aux_and_layer{iLevel}(i_node);
            %% empty
            ch1 = [];ch2=[];
            if node(1)~=0 && node(2) ~=0
                ch1 = orLayer{node(1)}(node(2));
            end
            if node(3)~=0 && node(4) ~=0
                ch2 = orLayer{node(3)}(node(4));
            end
            %% push the two child or node into open list( list of nodes to explore);
            if aux_node.diffInDepth ==0
                if ~isempty(ch2)
                    ch2.org_index = node(4);
                    ch2.org_argmax = ch2.argmax;
                    res_or_layer{node(3)}=[res_or_layer{node(3)}; ch2];
                end
                if ~isempty(ch1)
                    ch1.org_index = node(2);
                    ch1.org_argmax = ch1.argmax;
                    res_or_layer{node(1)}=[res_or_layer{node(1)}; ch1];
                end
            elseif aux_node.diffInDepth ==1
                ch1.org_index = node(2);
                ch1.org_argmax = ch1.argmax;
                res_or_layer{node(1)}=[res_or_layer{node(1)}; ch1];
            elseif aux_node.diffInDepth ==2
                ch2.org_index = node(4);
                ch2.org_argmax = ch2.argmax;
                res_or_layer{node(3)}=[res_or_layer{node(3)}; ch2];
            end
        end
    end
    
    
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %   return results
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    resTree.andLayer = res_and_layer;
    resTree.orLayer = res_or_layer;
    resTree.termLayer = res_term_layer;
    
    resTrees{i_val_and} = resTree;
    
    
    
    %{
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %  Section 3, auxilary function to plot the tree
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    color_list = ['red','teal','moccasin','gold','deeppink','lawngreen'];
    
    pFile = fopen('showAoT.dot','r+');
    if pFile==-1
        disp('can not open showAoT.dot!\n Will return without saving results');
        return;
    end
    % erase the last line ending the graph file
    fseek(pFile,-2,'eof');
    for iLevel = nLevel:-1:1
        n_node = length(res_or_layer{iLevel});
        for i_node = 1:n_node
            node = res_or_layer{iLevel}(i_node);
            or_node_name = sprintf('O_%d_%d',iLevel,node.org_index);
            if node.argmax ==0
                chd_name = sprintf('T_%d_%d',iLevel,node.org_index);
            else
                chd_name = sprintf('A_%d_%d',iLevel,node.org_argmax);
            end
            
            % nodes in red
            fprintf(pFile,'%s [color = "%s"]\n',or_node_name,color_list(i_val_and));
            fprintf(pFile,'%s [color = "%s"]\n',chd_name,color_list(i_val_and));
            % edge in red
            fprintf(pFile,'%s -> %s [color = "%s"]\n',or_node_name,chd_name,color_list(i_val_and));
            
            if node.argmax~=0
                chd = res_and_layer{iLevel}(node.argmax,:);
                if chd(1)~=0 && chd(2)~=0
                    fprintf(pFile,'%s -> O_%d_%d [color = "%s"]\n',...
                        chd_name,chd(1),chd(2),color_list(i_val_and));
                end
                if chd(3)~=0 && chd(4)~=0
                    fprintf(pFile,'%s -> O_%d_%d [color = "%s"]\n',...
                        chd_name,chd(3),chd(4),color_list(i_val_and));
                end
            end
            
        end
    end
    
    % add file end
    fprintf(pFile,'}\n');
    
    fclose(pFile);
    %}
end% i_val_and






